#include "main/utils.h"
using namespace std;

class Solution {
  public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
      auto sort_interval = [](vector<int>& a, vector<int>& b) -> bool {
        return a[0] < b[0];
      };
      sort(intervals.begin(), intervals.end(), sort_interval);
      vector<vector<int>> outputs;
      outputs.push_back(intervals[0]);
      for (auto interval : intervals) {
        auto tmp = outputs.back();
        if (interval[0] <= tmp[1] && interval[1] > tmp[1]) {
          tmp[1] = interval[1];
          outputs.pop_back();
          outputs.push_back(tmp);
        } else if (interval[0] > tmp[1]) {
          outputs.push_back(interval);
        }
      }
      return outputs;
    }
};

int main() {
  vector<vector<int>> input = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
  Solution su;
  auto output = su.merge(input);
  printVec("output", output);
}
